package cn.edu.xjtu.work.climbStairs;

/**
 * 70. 爬楼梯
 * 
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 
 * 注意：给定 n 是一个正整数。
 */
public class Solution {
  /**
   * 动态规划
   * 
   * f(x)=f(x−1)+f(x−2),有两种方式到达x级,分别是走一个和走两个,因此到达x级的方案数为两种爬法的和
   * 
   * 初始条件为f(0)=1;f(1)=1;
   * 
   * @param n
   * @return
   */
  public int climbStairs(int n) {
    if (n == 0 || n == 1) {
      return 1;
    }
    int p = 1;
    int q = 1;
    int s = 0;
    for (int i = 2; i <= n; i++) {
      s = p + q;
      q = p;
      p = s;
    }
    return s;
  }
}
